/* cdsl_map.c
 * Copyright (c) 2009 Charles S. Wilson
 *
 * Permission is hereby granted, free of charge, to any person
 * obtaining a copy of this software and associated documentation
 * files (the "Software"), to deal in the Software without
 * restriction, including without limitation the rights to use,
 * copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the
 * Software is furnished to do so, subject to the following
 * conditions:
 *
 * The above copyright notice and this permission notice shall be
 * included in all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
 * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
 * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
 * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
 * OTHER DEALINGS IN THE SOFTWARE.
 */
#include <stdlib.h>
#include <assert.h>
#include "cdsl_map.h"

struct cdsl_map_data
  {
    void *             key;
    void *             val;
  };

typedef struct cdsl_map_userdata
  {
    cdsl_map_key_cmp_f kcmp;
    cdsl_map_key_dup_f kdup;
    cdsl_map_key_rel_f krel;
    cdsl_map_val_dup_f vdup;
    cdsl_map_val_rel_f vrel;
  } cdsl_map_userdata_t;


void *
cdsl_map_key_data (cdsl_map_data_t *data)
{
  return (data ? data->key : NULL);
}

void *
cdsl_map_value_data (cdsl_map_data_t *data)
{
  return (data ? data->val : NULL);
}

static inline cdsl_map_data_t *
cdsl_map_get_data (cdsl_map_iter_t *iter)
{
  return (cdsl_map_data_t *) cdsl_rbtdata (iter);
}

void *
cdsl_map_key (cdsl_map_iter_t *iter)
{
  return cdsl_map_key_data (cdsl_map_get_data (iter));
}

void *
cdsl_map_value (cdsl_map_iter_t *iter)
{
  return cdsl_map_value_data (cdsl_map_get_data (iter));
}

cdsl_map_data_t *
cdsl_map_data_new (cdsl_map_t *self, void *key, void *value)
{
  cdsl_map_data_t * d = malloc (sizeof (cdsl_map_data_t));
  cdsl_map_userdata_t * ud = (cdsl_map_userdata_t *) cdsl_rb_getUD (self);
  d->key = ud->kdup (key);
  d->val = ud->vdup (value);
  return d;
}

static void
cdsl_map_data_delete_impl (const cdsl_rbtree_t *self, void *data)
{
  const cdsl_map_userdata_t * ud = (const cdsl_map_userdata_t *) cdsl_rb_getUD (
    (const cdsl_map_t *)self);
  cdsl_map_data_t *p = data;
  if (!p) return;
  ud->krel (p->key);
  ud->vrel (p->val);
  free (p);
}

void
cdsl_map_data_delete (cdsl_map_t *self, cdsl_map_data_t *data)
{
  cdsl_map_data_delete_impl ((const cdsl_rbtree_t *)self, (void *)data);
}

static void *
cdsl_map_data_dup_impl (const cdsl_rbtree_t *self, const void *data)
{
  cdsl_map_data_t * d = malloc (sizeof (cdsl_map_data_t));
  const cdsl_map_userdata_t * ud = (const cdsl_map_userdata_t *) cdsl_rb_getUD (
    (const cdsl_map_t *)self);
  const cdsl_map_data_t * s = (const cdsl_map_data_t *) data;

  if (s && s->key)
    d->key = ud->kdup (s->key);
  else
    d->key = NULL;

  if (s && s->val)
    d->val = ud->vdup (s->val);
  else
    d->val = NULL;

  return (void *)d;
}

cdsl_map_data_t *
cdsl_map_data_dup (const cdsl_map_t *self, const cdsl_map_data_t *data)
{
  return (cdsl_map_data_t *) cdsl_map_data_dup_impl (
    (const cdsl_rbtree_t *)self, (const void *)data);
}

static int
cdsl_map_cmp (const cdsl_rbtree_t *self, const void *d1, const void *d2)
{
  const cdsl_map_data_t * md1 = d1;
  const cdsl_map_data_t * md2 = d2;
  const cdsl_map_userdata_t * ud = (const cdsl_map_userdata_t *) cdsl_rb_getUD (
    (const cdsl_map_t *)self);
  if (!md1 && !md2) return  0; /* null     = null     */
  if (!md1)         return -1; /* null     < non-null */
  if (!md2)         return  1; /* non-null > null     */
  return ud->kcmp (md1->key, md2->key);
}

cdsl_map_t *
cdsl_map_new (cdsl_map_key_cmp_f kcmp,
              cdsl_map_key_dup_f kdup,
              cdsl_map_key_rel_f krel,
              cdsl_map_val_dup_f vdup,
              cdsl_map_val_rel_f vrel)
{
  cdsl_rbtree_t *map = cdsl_rbnew (&cdsl_map_cmp, &cdsl_map_data_dup_impl, &cdsl_map_data_delete_impl);
  cdsl_map_userdata_t * ud = (cdsl_map_userdata_t *) malloc (sizeof (cdsl_map_userdata_t));
  ud->kcmp = kcmp;
  ud->kdup = kdup;
  ud->krel = krel;
  ud->vdup = vdup;
  ud->vrel = vrel;
  (void) cdsl_rb_setUD (map, (void *)ud);
  return (cdsl_map_t *) map;
}

void
cdsl_map_delete (cdsl_map_t * map)
{
  cdsl_map_userdata_t * ud = (cdsl_map_userdata_t *) cdsl_rb_getUD (map);
  cdsl_rbdelete (map);
  free (ud);
}

void
cdsl_map_clear (cdsl_map_t * map)
{
  cdsl_rbclear ((cdsl_rbtree_t *) map);
}


int
cdsl_map_insert (cdsl_map_t *self, void *key, void *value)
{
  cdsl_map_userdata_t * ud __attribute__((unused)) =
    (cdsl_map_userdata_t *) cdsl_rb_getUD (self);
  cdsl_map_data_t d;
  d.key = key;
  d.val = value;
  return cdsl_rbinsert (self, &d);
}

int
cdsl_map_erase (cdsl_map_t *self, void *key)
{
  cdsl_map_data_t d;
  d.key = key;
  d.val = NULL; /* doesn't matter */
  return cdsl_rberase ((cdsl_rbtree_t *)self, (void *)&d);
}

int
cdsl_map_find (cdsl_map_t *self, void *key, cdsl_map_iter_t *iter)
{
  cdsl_map_data_t * d;
  cdsl_map_userdata_t * ud = (cdsl_map_userdata_t *) cdsl_rb_getUD (self);

  cdsl_rbtfirst (iter, self);
  d = (cdsl_map_data_t *) cdsl_map_get_data (iter);
  while (d != NULL)
    {
      int cmp = ud->kcmp (cdsl_map_key_data (d), key);
      if (cmp == 0)
        break;

      d = (cdsl_map_data_t *) cdsl_rbtnext (iter);
    }
  return (d != NULL);
}

size_t
cdsl_map_size (cdsl_map_t *self)
{
  return cdsl_rbsize (self);
}

int
cdsl_map_empty (cdsl_map_t *self)
{
  return (cdsl_rbsize (self) == (size_t)0);
}

cdsl_map_iter_t *
cdsl_map_iter_new    (cdsl_map_t *self)
{
  return (cdsl_map_iter_t *) cdsl_rbtnew ();
}

void
cdsl_map_iter_delete (cdsl_map_iter_t * iter)
{
  cdsl_rbtdelete ((cdsl_rbtrav_t *)iter);
}

void
cdsl_map_first (cdsl_map_t *self, cdsl_map_iter_t *iter)
{
  (void) cdsl_rbtfirst ((cdsl_rbtrav_t *)iter, (cdsl_rbtree_t *)self);
}

void
cdsl_map_last (cdsl_map_t *self, cdsl_map_iter_t *iter)
{
  (void) cdsl_rbtlast ((cdsl_rbtrav_t *)iter, (cdsl_rbtree_t *)self);
}

void
cdsl_map_next (cdsl_map_iter_t *iter)
{
  (void) cdsl_rbtnext ((cdsl_rbtrav_t *)iter);
}

void
cdsl_map_prev (cdsl_map_iter_t *iter)
{
  (void) cdsl_rbtprev ((cdsl_rbtrav_t *)iter);
}

int
cdsl_map_iter_end (cdsl_map_iter_t *iter)
{
  return (cdsl_rbtdata (iter) == NULL);
}


